package work.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Problem56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });


        List<int[]> ans = new ArrayList<>();
        for (int[] temp : intervals) {
            int m = ans.size();
            if (m > 0 && temp[0] <= ans.get(m - 1)[1]) {
                int[] elemnt = new int[2];
                elemnt[0] = ans.get(m - 1)[0];
                elemnt[1] = Math.max(ans.get(m - 1)[1], temp[1]);
                ans.set(m - 1, elemnt);
            } else ans.add(temp);
        }
        return ans.toArray(new int[ans.size()][]);
    }



    public static void main(String[] args) {
        Problem56 problem = new Problem56();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] mergedIntervals = problem.merge(intervals);
        System.out.println(Arrays.deepToString(mergedIntervals));
    }
}
